Master Theorem Examples

Examples#

The following are some examples of the master theorem. Let’s look at them one by one.

Example 1#

This is the case of merge sort. Its time complexity is $T(n)$ = $2 T(n/2)$ + $n$.

Solution

In this example, $a$ and $b$ are both equal to 2. So, $log_ba$ = $log_22$ = 1 which means that $f(n)$ = n = $\Theta(n^{log_22}.log^0n)$. That means case 2 is applied and $T(n)$ = $\Theta(n^{log_22}.log^{0+1}n)$. Its final time complexity is $T(n)$ = $\Theta(n.log(n))$.

Example 2#

This is a case of binary search. Its time complexity is $T(n)$ = $T(n/2)$ + $k$.

Solution

In this example, $a$ is equal to 1 and $b$ is equal to 2. So, $log_ba$ = $log_21$ = 0 which means that $f(n)$ = k = $\Theta(n^{log_21}.log^0n)$. That means case 2 is applied and $T(n)$ = $\Theta(n^{log_21}.log^{0+1}n)$. Its final time complexity is $T(n)$ = $\Theta(log(n))$.

Example 3#

This is a case of binary tree traversal. Its time complexity is $T(n)$ = 2$T(n/2)$ + $k$.

Solution

In this example, $a$ is equal to 2 and $b$ is also equal to 2. So, $log_ba$ = $log_22$ = 1 which means that $f(n)$ = k = $O(n^{log_22-1})$. That means case 1 is applied and $T(n)$ = $\Theta(n^{log_22})$. Its final time complexity is $T(n)$ = $\Theta(n)$.

Example 4#

In this example, an algorithm has a time complexity of $T(n)$ = 2$T(n/2)$ + $n^2$.

Solution

In this example, $a$ is equal to 2 and $b$ is also equal to 2. So, $log_ba$ = $log_22$ = 1 which means that $f(n)$ = $n^2$ = $\Omega(n^{log_22+1})$. That means case 3 is applied and $T(n)$ = $\Theta(f(n))$. Its final time complexity is $T(n)$ = $\Theta(n^2)$.

Let’s test what we’ve learned so far with a quick assessment.

Example 5#

In this example, an algorithm has a time complexity of $T(n)$ = $T(n/2)$ + $2n$.

Solution

In this example, $a$ is equal to 1 and $b$ is equal to 2. So, $log_ba$ = $log_21$ = 0 which means that $f(n)$ = $2n$ = $\Omega(n^{log_21+1})$. That means case 3 is applied. Its final time complexity is $T(n)$ = $\Theta(n)$.

Example 6#

In this example, an algorithm has a time complexity of $T(n)$ = 16 $T(n/4)$ + $n$.

Solution

In this example, $a$ is equal to 16 and $b$ is equal to 4. So, $log_ba$ = $log_416$ = 2 which means that $f(n)$ = $n$ = $O(n^{log_416-1})$. That means case 1 is applied. Its final time complexity is $T(n)$ = $\Theta(n^2)$.

Example 7#

In this example, an algorithm has a time complexity of $T(n)$ = 2 $T(n/2)$ + $nlog(n)$.

Solution

In this example, $a$ is equal to 2 and $b$ is equal to 2. So, $log_ba$ = $log_22$ = 1 which means that $f(n)$ = $nlog(n)$ = $\Theta(n^{log_22}log^1n)$. That means case 2 is applied. Its final time complexity is $T(n)$ = $\Theta(n^{log_22}log^{1+1}n)$ = $\Theta(n.log^2(n))$.

Example 8#

In this example, an algorithm has a time complexity of $T(n)$ = 2 $T(n/4)$ + $n^{0.5}$ .

Solution

In this example, $a$ is equal to 2 and $b$ is equal to 4. So, $log_ba$ = $log_42$ = 0.5 which means that $f(n)$ = $n^{0.5}$ = $\Theta(n^{log_42}log^0n)$. That means case 2 is applied. Its final time complexity is $T(n)$ = $\Theta(n^{log_42}log^{0+1}n)$ = $\Theta(n^{0.5}.log(n))$.

Example 9#

In this example, an algorithm has a time complexity of $T(n)$ = 3 $T(n/3)$ + $√ n$ .

Solution

In this example, $a$ is equal to 3 and $b$ is also equal to 3. So, $log_ba$ = $log_33$ = 1 which means that case 1 is applied. Its final time complexity is $T(n)$ = $\Theta(n)$.

Example 10#

In this example, an algorithm has a time complexity of $T(n)$ = 3 $T(n/4)$ + $nlog(n)$ .

Solution

In this example, $a$ is equal to 3 and $b$ is equal to 4. So, $log_ba= log_43 = 0.79$ which means that $f(n)$ = $nlog(n)$ = $\Omega(n^{log_43}log^1n)$. By applying logarithmic rules we know that n > $n^{log_43}$ or $n^{log_44}$ > $n^{log_43}$ or $log(4)$ > $log(3)$ Case 3 is applied . Its final time complexity will be $T(n)$ = $\Theta(n.log(n))$.